
class ListNode(var `val`: Int) {
    var next: ListNode? = null
}


class Solution {
    /**
     * 解法一，将val变为一个标记，再次碰到说明是环形
     */
    fun hasCycle(head: ListNode?): Boolean {
        var currNode = head
        while(currNode!=null){
            if(currNode.`val` == 100001){
                return true
            }else{
                currNode.`val` = 100001
                currNode = currNode.next    
            }
        }

        return false
    }

    /**
     * 解法二，快慢双指针，最终总会遇到
     */
     fun hasCycle2(head: ListNode?): Boolean {
        if(head==null || head.next == null){
            return false
        }
        var slowNode = head
        var fastNode = head.next

        while(true){
            if(fastNode == slowNode){
                return true
            }

            if(fastNode!=null && fastNode.next!=null && fastNode.next.next!=null){
                   fastNode = fastNode.next.next
            }else{
                return false
            }

            slowNode = slowNode!!.next
        }

        return false
    }

    /**
     * 解法三 存到set集合中，通过如果已存在，证明有环
     */

     fun hasCycle2(head: ListNode?): Boolean {
        if(head==null || head.next == null){
            return false
        }
        val set =HashSet<ListNode>()
        var currNode = head
        while(currNode!=null){
            if(set.contains(currNode)){
                return true
            }
            set.add(currNode)
            currNode = currNode!!.next
        }

        return false
    }
}